package com.gaogzhen.algorithms4.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 堆排序
 *  默认使用最大堆从小到大排序
 *  传入从大到小比较器为使用最小堆从大到小排序
 * @author Administrator
 * @date 2022-12-06 22:15
 */
public class Heap {

    /**
     * 比较器
     *  默认从小到大
     */
    private static Comparator<Comparable> comparator = Comparable::compareTo;

    /**
     * 堆排序
     * @param a             数组
     * @param comparator    比较器
     */
    public static void sort(Comparable[] a, Comparator<Comparable> comparator) {
        Heap.comparator = comparator;
        sort(a);
    }

    /**
     * 堆排序，默认最大堆，从小到大排序
     * @param a 数组
     */
    public static void sort(Comparable[] a) {
        int s = a.length - 1;
        for (int i = (s - 1) / 2 ; i >= 0; i--) {
            sink(a, i, s);
        }
        while (s > 0) {
            exch(a, 0, s--);
            sink(a, 0, s);
        }
    }

    /**
     * 下沉元素
     * @param a 二叉堆
     * @param i 下沉元素索引
     * @param s 最大索引
     */
    private static void sink(Comparable[] a, int i, int s) {
        while (2 * ( i+1 ) - 1 <= s) {
            int j = 2 * (i + 1) - 1;
            if (j < s && compare(a, j, j+1)) j++;
            if (!compare(a, i, j)) break;
            exch(a, i, j);
            i = j;
        }
    }

    /**
     * 交换元素
     * @param a 数组
     * @param i 索引
     * @param j 索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        // 索引-1目的使堆索引对应数组0开始的索引
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 比较数组2个位置元素
     * @param a 数组
     * @param i 索引
     * @param j 索引
     * @return
     */
    private static boolean compare(Comparable[] a, int i, int j) {
        return comparator.compare(a[i], a[j]) < 0;
    }

    public static void main(String[] args) {
        Integer[] a = {-1, 132, 234, 2, 22, 92992, 992, 991};
        // 从小到大排序
        sort(a);
        // 从大到小排序
//        sort(a, ((o1, o2) -> o2.compareTo(o1)));
        System.out.println(Arrays.toString(a));
    }
}
